AtCoder AGC 040 A - >< (300 点)
長さ $ N−1の文字列$ S が与えられます． $ Sの各文字は $ '<' または $ '>' です．
$ S_i='<' のとき：$ a_i < a_{i+1}
$ S_i='>' のとき：$ a_i > a_{i+1}
この良い非負整数列の要素の総和としてありうる最小の値を求めてください．
考察履歴
同じ数字を使っても良いので最小になるような数列は素朴に作れそう
$ ><で挟まれる場所は0にすれば良い
そこから左右に同じ符号が続く限り$ +1していけば最小となる数列ができそう
入力例2で手作業で計算してみたら、それで出力例と合致することを確認
$ 0<3>2>1>0<1<2>0<1<2<3<4<5>2>1>0<1で総和は$ 28となる
この数列の和を求めるアルゴリズムはどのようになるか？
これで実装に入ったが、出力例に合致せず、考察不足
足してはいけない部分まで足し込んでいる、場合分けが必要 先端が開いている$ >の場合、真ん中で$ <>となっている場合、終端で開いている$ <場合の3パターンが必要
真ん中部分はさらに、$ <側と$ >側で大きい値と小さい値がどちらか判定する
大きい値の方は$ n(n+1)/2
小さい値の方は$ n(n-1)/2
先端と終端は$ n(n+1)/2
これらの値を合計した値が解答
実装
Pythonで文字列問題を連続して解いていたので気分転換にRustで実装
そのVecを制御するのがPythonとはだいぶ勝手が違う
真ん中部分の状態をチエックしていくのにwindows().map()を利用
そしてそこで得たイテレータをsum()で足し込む
終端の処理では、終端の値を得るためにlast()を利用し、Some()で受ける
Pythonに比べるとコード量多くなるが安全に実装していて安心感がある
ACコード
code:rust
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn rle(s: Vec<char>) -> Vec<(char, u64)> {
let mut res: Vec<(char, u64)> = Vec::new();
let mut pre = ' ';
let mut chain = 1;
for c in s.into_iter() {
if c == pre {
chain += 1;
} else {
if pre != ' ' {
res.push((pre, chain));
}
pre = c;
chain = 1;
}
}
res.push((pre, chain));
res
}
fn main() {
let s: Vec<char> = read::<String>().chars().collect();
let rle = rle(s);
let mut ans = 0;
//println!("{:?}", rle);
//先端の処理
ans += (rle0.1 * (rle0.1 + 1)) / 2; }
.windows(2)
.map(|v| {
let mut res = 0;
if v0.0 == '<' && v1.0 == '>' { res += (v0.1 * (v0.1 + 1)) / 2; res += (v1.1 * (v1.1 - 1)) / 2; }else{
res += (v0.1 * (v0.1 - 1)) / 2; res += (v1.1 * (v1.1 + 1)) / 2; }
}
res
})
.sum();
//println!("{}", mid_ans);
ans += mid_ans;
//終端の処理
if let Some(v) = rle.last() {
if v.0 == '<' {
ans += (v.1 * (v.1 + 1)) / 2;
}
}
println!("{}", ans);
}
結構難しく感じたが400台diffでビビる
連続で同じ分野の問題を解いている。ランダムに選んでいるのに、なぜ。。。